package leetcode.f1t100;

import java.util.HashMap;

/**
 * 寻找不重复的子串最大长度
 *
 * https://leetcode.com/problems/longest-substring-without-repeating-characters/
 *
 * @author lichx
 * @date 2021/9/15 10:01
 */
public class Q3_LongestSubStringWithoutSC {

    public static void main(String[] args) {
        System.out.println(lengthOfLongestSubstring("abcedefgabc"));
    }
    public static int lengthOfLongestSubstring(String s) {
        char[] c = s.toCharArray();
        int ans = 0;
        int l = 0;
        int r = 0;
        int debt = 0;
        HashMap<Character,Integer> dict = new HashMap<>();
        while(r < s.length()){
            if(putDict(dict, c[r]) > 1){
                debt ++;
                while(l<=r){
                    if(popDict(dict, c[l++]) == 1){
                        debt--;
                        break;
                    }
                }
            }else{
                if(debt == 0){
                    ans = Math.max(ans,r-l+1);
                }
            }
            r++;
        }
        return ans;
    }
    public static int putDict(HashMap<Character,Integer> dict,char c){
        if(dict.containsKey(c)){
            dict.put(c,dict.get(c)+1);
        }else{
            dict.put(c,1);
        }
        return dict.get(c);
    }
    public static int popDict(HashMap<Character,Integer> dict,char c){
        dict.put(c,dict.get(c)-1);
        return dict.get(c);
    }
}
